package com.aug_leo.datastructure.linkedlist;

/**
 * 合并多个有序链表
 */
public class E07Leetcode23 {

    // 合并两个有序链表
    public ListNode mergeTwoLists(ListNode pointer1, ListNode pointer2) {
        // 创建一个哨兵节点作为合并后链表的头部
        ListNode sentinel = new ListNode(-1, null);
        // 初始化一个指针指向哨兵
        ListNode pointer = sentinel;

        // 遍历两个连败哦直到一个为null
        while (pointer1 != null && pointer2 != null) {
            // 比较两个链表当前节点的值，选择较小的一个继续合并
            if (pointer1.val < pointer2.val) {
                // 如果第一个链表当前节点的值比较小，将其链接到合并后的链表
                pointer.next = pointer1;
                // 将第一个链表的指针向后移动
                pointer1 = pointer1.next;

            } else {
                // 如果第二个链表当前节点的值较小或相等，将其链接到合并后的链表
                pointer.next = pointer2;
                // 将第二个链表的指针向后移动
                pointer2 = pointer2.next;

            }
            // 将合并后的链表指针向后移动
            pointer = pointer.next;
        }

        // 当第一个链表遍历完成后，直接将另一个链表剩余的部分链接到合并后的链表末尾
        if (pointer1 != null) {
            pointer.next = pointer1;
        }

        if (pointer2 != null) {
            pointer.next = pointer2;
        }

        // 返回合并后链表的头节点
        return sentinel.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {

            return null;
        }
        return split(lists, 0, lists.length - 1);
    }

    /**
     * @param lists 链表数组，包含了多个待合并的链表
     * @param i     分割的起始索引
     * @param j     分割的结束索引
     * @return 合并后的链表的头节点
     */
    private ListNode split(ListNode[] lists, int i, int j) {
        if (i == j) { // 数组内只有一个链表
            return lists[i];
        }
        // 计算中间索引
        int mid = (i + j) >>> 1;
        // 递归地分割链表数组为两半
        ListNode left = split(lists, i, mid);
        ListNode right = split(lists, mid + 1, j);
        // 合并左右两半链表，并返回合并后的链表头节点
        return mergeTwoLists(left, right);
    }

    /**
     * <h3>Divide and Conquer 分而治之（分、治、合）</h3>
     * <h3>Decrease and Conquer 减而治之</h3>
     */

    public static void main(String[] args) {
        ListNode[] lists = {
                ListNode.of(1, 4, 5),
                ListNode.of(1, 3, 4),
                ListNode.of(2, 6)
        };
        ListNode m = new E07Leetcode23().mergeKLists(lists);
        System.out.println(m);
    }
}
